#include "Grammatical.h"

void grammatical::bootGrammatical() {
    dict = {
        {"CompUnit", 1},
        {"Decl", 2},
        {"FuncDef", 3},
        {"MainFuncDef", 4},
        {"ConstDecl", 5},
        {"VarDecl", 6},
        {"FuncType", 7},
        {"Ident", 8},
        {"FuncFParams", 9},
        {"Block", 10},
        {"BType", 11},
        {"VarDef", 12},
        {"FuncFParam", 13},
        {"BlockItem", 14},
        {"ConstExp", 15},
        {"InitVal", 16},
        {"Stmt", 17},
        {"AddExp", 18},
        {"AddExpS", 76},
        {"Exp", 19},
        {"LVal", 20},
        {"Cond", 21},
        {"FormatString", 22},
        {"MulExp", 23},
        {"MulExpS", 77},
        {"LOrExp", 24},
        {"LOrExpS", 78},
        {"LAndExp", 25},
        {"LAndExpS", 79},
        {"EqExp", 26},
        {"EqExpS", 80},
        {"UnaryExp", 27},
        {"RelExp", 28},
        {"RelExpS", 81},
        {"PrimaryExp", 32},
        {"FuncRParams", 33},
        {"Number", 34},
        {"IntConst", 35},
        {"decimal-const", 36},
        {"nonzero-digit", 37},
        {"UnaryOp", 38},
        {"ConstInitVal", 39},
        {"ConstDef", 40},
        {"main", 41},
        {"const", 42},
        {"int", 43},
        {"break", 44},
        {"continue", 45},
        {"if", 46},
        {"else", 47},
        {"!", 48},
        {"&&", 49},
        {"||", 50},
        {"while", 51},
        {"getint", 52},
        {"printf", 53},
        {"return", 54},
        {"+", 55},
        {"-", 56},
        {"void", 57},
        {"*", 58},
        {"/", 59},
        {"%", 60},
        {"<", 61},
        {"<=", 62},
        {">", 63},
        {">=", 64},
        {"==", 65},
        {"!=", 66},
        {"=", 67},
        {";", 68},
        {",", 69},
        {"(", 70},
        {")", 71},
        {"[", 72},
        {"]", 73},
        {"{", 74},
        {"}", 75}
    };
}

void grammatical::rollback(int size)
{
	while (answer.size() > size)
		answer.pop_back();
}

std::pair<int, bool> grammatical::matchType(int type, int position)
{
	if (position == words.size())
		return {position, true};
	std::pair<int, bool> original_pos = {position, false};
	std::pair<int, bool> newposition;
	int size = answer.size();
	switch (type)
	{
	case 1: // CompUnit ::= {Decl} {FuncDef} MainFuncDef （0到正无穷）
		newposition = matchType(dict["Decl"], position);
		// if second false, return original_pos 0
		// if second true, return newposition 1 or 1+...
		while (newposition.second)
		{
			position = newposition.first;
			newposition = matchType(dict["Decl"], position);
		}

		newposition = matchType(dict["FuncDef"], position);
		while (newposition.second)
		{
			position = newposition.first;
			newposition = matchType(dict["FuncDef"], position);
		}

		newposition = matchType(dict["MainFuncDef"], position);
		// if second false, return original_pos 0
		// if second true, return MainFuncDef correlation
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;
		answer.push_back({"CompUnit", ""});
		return {position, true};
		break;
	case 2: // Decl（特选）
		newposition = matchType(dict["ConstDecl"], position);
		// if second false, return original_pos 0
		// if second true, return ConstDecl correlation
		if (newposition.second)
			return newposition;

		newposition = matchType(dict["VarDecl"], position);
		// if second false, return original_pos 0
		// if second true, return VarDecl correlation
		if (newposition.second)
			return newposition;

		rollback(size);
		return original_pos;
		break;
	case 3: // FuncDef (串行)
		newposition = matchType(dict["FuncType"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		// 锁定上一次匹配成功的位置
		position = newposition.first;

		// 在匹配成功后继续匹配
		newposition = matchType(dict["Ident"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["("], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		position = matchType(dict["FuncFParams"], position).first;

		newposition = matchType(dict[")"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["Block"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"FuncDef", ""});
		return {position, true};
		break;
	case 4: // MainFuncDef
		newposition = matchType(dict["int"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["main"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["("], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict[")"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["Block"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"MainFuncDef", ""});
		return {position, true};
		break;
	case 5: // ConstDecl（，cycle 0到正无穷）
		newposition = matchType(dict["const"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["BType"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["ConstDef"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict[","], position);
		while (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["ConstDef"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;
			newposition = matchType(dict[","], position);
		}
		newposition = matchType(dict[";"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"ConstDecl", ""});
		return {position, true};
		break;
	case 6: // VarDecl
		newposition = matchType(dict["BType"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["VarDef"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict[","], position);
		while (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["VarDef"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict[","], position);
		}

		newposition = matchType(dict[";"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"VarDecl", ""});
		return {position, true};
		break;
	case 7: // FuncType（终端）
		newposition = matchType(dict["void"], position);
		if (newposition.second)
		{
			answer.push_back({"FuncType", ""});
			return newposition;
		}

		newposition = matchType(dict["int"], position);
		if (newposition.second)
		{
			answer.push_back({"FuncType", ""});
			return newposition;
		}
		newposition = matchType(dict["float"], position);

		if (newposition.second)
		{
			answer.push_back({"FuncType", ""});
			return newposition;
		}

		rollback(size);
		return original_pos;
		break;
	case 8: // Ident (Part and Overall)
		if (words[position].first == "IDENFR")
		{
			answer.push_back(words[position]);
			return {position + 1, true};
		}
		rollback(size);
		return original_pos;
		break;
	case 9: // FuncFParams
		newposition = matchType(dict["FuncFParam"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict[","], position);
		while (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["FuncFParam"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict[","], position);
		}
		answer.push_back({"FuncFParams", ""});
		return {position, true};
		break;
	case 10: // Block
		newposition = matchType(dict["{"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["BlockItem"], position);
		while (newposition.second)
		{
			position = newposition.first;
			newposition = matchType(dict["BlockItem"], position);
		}

		newposition = matchType(dict["}"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"Block", ""});

		return {position, true};
		break;
	case 11: // BType
		newposition = matchType(dict["int"], position);
		if (newposition.second)
			return newposition;

		newposition = matchType(dict["float"], position);
		if (newposition.second)
			return newposition;

		rollback(size);
		return original_pos;
		break;
	case 12: // VarDef
		newposition = matchType(dict["Ident"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["["], position);
		while (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["ConstExp"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["]"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["["], position);
		}

		newposition = matchType(dict["="], position);
		if (!newposition.second)
		{
			answer.push_back({"VarDef", ""});
			return {position, true};
		}
		position = newposition.first;

		newposition = matchType(dict["InitVal"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"VarDef", ""});
		return {position, true};
		break;
	case 13: // FuncFParam（方括号内的成分为任选项）,部分可选
		newposition = matchType(dict["BType"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["Ident"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["["], position);
		if (!newposition.second)
		{
			answer.push_back({"FuncFParam", ""});
			return {position, true};
		}
		position = newposition.first;

		newposition = matchType(dict["]"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["["], position);
		while (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["ConstExp"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["]"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["["], position);
		}

		answer.push_back({"FuncFParam", ""});
		return {position, true};
		break;
	case 14: // BlockItem
		newposition = matchType(dict["Decl"], position);
		if (newposition.second)
			return newposition;

		newposition = matchType(dict["Stmt"], position);
		if (newposition.second)
			return newposition;

		rollback(size);
		return original_pos;
		break;
	case 15: // ConstExp
		newposition = matchType(dict["AddExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"ConstExp", ""});
		return {position, true};
		break;
	case 16: // InitVal (Choice1,multiple)
		newposition = matchType(dict["Exp"], position);
		if (newposition.second)
		{
			answer.push_back({"InitVal", ""});
			return newposition;
		}

		newposition = matchType(dict["{"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["InitVal"], position);
		if (newposition.second)
		{
			position = newposition.first;
			newposition = matchType(dict[","], position);
			while (newposition.second)
			{
				position = newposition.first;

				newposition = matchType(dict["InitVal"], position);
				if (!newposition.second)
				{
					rollback(size);
					return original_pos;
				}
				position = newposition.first;
				newposition = matchType(dict[","], position);
			}
		}
		newposition = matchType(dict["}"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"InitVal", ""});
		return {position, true};
		break;
	case 17: // Stmt
		newposition = matchType(dict["LVal"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["="], position);
			if (newposition.second)
			{
				position = newposition.first;

				newposition = matchType(dict["Exp"], position);
				if (newposition.second)
				{
					position = newposition.first;

					newposition = matchType(dict[";"], position);
					if (!newposition.second)
					{
						rollback(size);
						return original_pos;
					}
					position = newposition.first;

					answer.push_back({"Stmt", ""});
					return {position, true};
				}

				newposition = matchType(dict["getint"], position);
				if (!newposition.second)
				{
					rollback(size);
					return original_pos;
				}
				position = newposition.first;

				newposition = matchType(dict["("], position);
				if (!newposition.second)
				{
					rollback(size);
					return original_pos;
				}
				position = newposition.first;

				newposition = matchType(dict[")"], position);
				if (!newposition.second)
				{
					rollback(size);
					return original_pos;
				}
				position = newposition.first;

				newposition = matchType(dict[";"], position);
				if (!newposition.second)
				{
					rollback(size);
					return original_pos;
				}
				position = newposition.first;

				answer.push_back({"Stmt", ""});
				return {position, true};
			}
		}
		position = original_pos.first;
		rollback(size);
		newposition = matchType(dict["Block"], position);
		if (newposition.second)
		{
			answer.push_back({"Stmt", ""});
			return newposition;
		}
		newposition = matchType(dict["if"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["("], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["Cond"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict[")"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["Stmt"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["else"], position);
			if (newposition.second)
			{
				position = newposition.first;
				newposition = matchType(dict["Stmt"], position);
				if (!newposition.second)
				{
					rollback(size);
					return original_pos;
				}
				position = newposition.first;
				answer.push_back({"Stmt", ""});
				return {position, true};
			}
			else
			{
				answer.push_back({"Stmt", ""});
				return {position, true};
			}
		}
		newposition = matchType(dict["while"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["("], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["Cond"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict[")"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["Stmt"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;
			answer.push_back({"Stmt", ""});
			return {position, true};
		}
		newposition = matchType(dict["break"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict[";"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;
			answer.push_back({"Stmt", ""});
			return {position, true};
		}
		newposition = matchType(dict["continue"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict[";"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;
			answer.push_back({"Stmt", ""});
			return {position, true};
		}
		newposition = matchType(dict["return"], position);
		if (newposition.second)
		{
			position = newposition.first;

			position = matchType(dict["Exp"], position).first;

			newposition = matchType(dict[";"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;
			answer.push_back({"Stmt", ""});
			return {position, true};
		}
		newposition = matchType(dict["printf"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["("], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["FormatString"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict[","], position);
			while (newposition.second)
			{
				position = newposition.first;

				newposition = matchType(dict["Exp"], position);
				if (!newposition.second)
				{
					rollback(size);
					return original_pos;
				}
				position = newposition.first;

				newposition = matchType(dict[","], position);
			}

			newposition = matchType(dict[")"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict[";"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;
			answer.push_back({"Stmt", ""});
			return {position, true};
		}
		position = matchType(dict["Exp"], position).first;

		newposition = matchType(dict[";"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"Stmt", ""});
		return {position, true};
		break;

		// AddExp->MulExp AddExpS
		// AddExpS->('+'|'-')MulExp AddExpS | e

	case 18: // AddExp
		newposition = matchType(dict["MulExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["AddExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"AddExp", ""});
		return {position, true};
		break;
	case 76: // AddExpS
		answer.push_back({"AddExp", ""});
		if (matchType(dict["+"], position).second)
			position++;
		else if (matchType(dict["-"], position).second)
			position++;
		else
		{
			answer.pop_back();
			return {position, true};
		}

		newposition = matchType(dict["MulExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["AddExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		return {position, true};
		break;
	case 19: // Exp
		newposition = matchType(dict["AddExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"Exp", ""});
		return {position, true};
		break;
	case 20: // LVal
		newposition = matchType(dict["Ident"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["["], position);
		while (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["Exp"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["]"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["["], position);
		}
		answer.push_back({"LVal", ""});
		return {position, true};
		break;
	case 21: // Cond
		newposition = matchType(dict["LOrExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"Cond", ""});
		return {position, true};
		break;
	case 22: // FormatString
		if (words[position].first == "STRCON")
		{
			answer.push_back(words[position]);
			return {position + 1, true};
		}
		else
			return {position, false};
		break;

	// MulExp->UnaryExp MulExpS
	// MulExpS->('*'|'/'|'%')UnaryExp MulExpS | e
	case 23: // MulExp
		newposition = matchType(dict["UnaryExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["MulExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"MulExp", ""});
		return {position, true};
		break;
	case 77: // MulExpS
		answer.push_back({"MulExp", ""});
		if (matchType(dict["*"], position).second)
			position++;
		else if (matchType(dict["/"], position).second)
			position++;
		else if (matchType(dict["%"], position).second)
			position++;
		else
		{
			answer.pop_back();
			return {position, true};
		}

		newposition = matchType(dict["UnaryExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["MulExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		return {position, true};
		break;

	// LOrExp->LAndExp LOrExpS
	// LOrExpS->'||'LAndExp LOrExpS | e
	case 24: // LOrExp
		newposition = matchType(dict["LAndExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["LOrExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"LOrExp", ""});
		return {position, true};
		break;
	case 78: // LOrExps
		answer.push_back({"LOrExp", ""});
		newposition = matchType(dict["||"], position);
		if (!newposition.second)
		{
			answer.pop_back();
			return {position, true};
		}
		position = newposition.first;

		newposition = matchType(dict["LAndExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["LOrExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		return {position, true};
		break;

	// LAndExp->EqExp LAndExpS
	// LAndExpS->'&&'EqExp LAndExpS | e
	case 25: // LAndExp
		newposition = matchType(dict["EqExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["LAndExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"LAndExp", ""});
		return {position, true};
		break;
	case 79: // LAndExpS
		answer.push_back({"LAndExp", ""});
		newposition = matchType(dict["&&"], position);
		if (!newposition.second)
		{
			answer.pop_back();
			return {position, true};
		}
		position = newposition.first;

		newposition = matchType(dict["EqExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["LAndExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		return {position, true};
		break;

	// EqExp->RelExp EqExpS
	// EqExpS->('=='|'!=')RelExp EqExpS | e
	case 26: // EqExp
		newposition = matchType(dict["RelExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["EqExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"EqExp", ""});
		return {position, true};
		break;
	case 80: // EqExpS
		answer.push_back({"EqExp", ""});
		if (matchType(dict["=="], position).second)
			position++;
		else if (matchType(dict["!="], position).second)
			position++;
		else
		{
			answer.pop_back();
			return {position, true};
		}

		newposition = matchType(dict["RelExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["EqExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		return {position, true};
		break;
	case 27: // UnaryExp

		newposition = matchType(dict["UnaryOp"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["UnaryExp"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			answer.push_back({"UnaryExp", ""});
			return {position, true};
		}

		newposition = matchType(dict["Ident"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["("], position);
			if (newposition.second)
			{
				position = newposition.first;

				position = matchType(dict["FuncRParams"], position).first;

				newposition = matchType(dict[")"], position);
				if (!newposition.second)
				{
					rollback(size);
					return original_pos;
				}
				position = newposition.first;
				answer.push_back({"UnaryExp", ""});
				return {position, true};
			}
		}

		position = original_pos.first;
		rollback(size);
		newposition = matchType(dict["PrimaryExp"], position);
		if (newposition.second)
		{
			answer.push_back({"UnaryExp", ""});
			return newposition;
		}
		else
		{
			rollback(size);
			return original_pos;
		}
		break;

	// RelExp->AddExp RelExpS
	// RelExpS->('<'|'>'|'<='|'>=')AddExp RelExpS | e
	case 28: // RelExp
		newposition = matchType(dict["AddExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["RelExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"RelExp", ""});
		return {position, true};
		break;
	case 81: // RelExps

		answer.push_back({"RelExp", ""});
		if (matchType(dict["<"], position).second)
			position++;
		else if (matchType(dict[">"], position).second)
			position++;
		else if (matchType(dict["<="], position).second)
			position++;
		else if (matchType(dict[">="], position).second)
			position++;
		else
		{
			answer.pop_back();
			return {position, true};
		}

		newposition = matchType(dict["AddExp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["RelExpS"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		return {position, true};
		break;
	case 32: // PrimaryExp
		newposition = matchType(dict["Number"], position);
		if (newposition.second)
		{
			answer.push_back({"PrimaryExp", ""});
			return newposition;
		}

		newposition = matchType(dict["LVal"], position);
		if (newposition.second)
		{
			answer.push_back({"PrimaryExp", ""});
			return newposition;
		}

		newposition = matchType(dict["("], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["Exp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict[")"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"PrimaryExp", ""});
		return {position, true};
		break;
	case 33: // FuncRParams
		newposition = matchType(dict["Exp"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict[","], position);
		while (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["Exp"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict[","], position);
		}
		answer.push_back({"FuncRParams", ""});
		return {position, true};
		break;
	case 34: // Number
		newposition = matchType(dict["IntConst"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;
		answer.push_back({"Number", ""});
		return {position, true};
		break;
	case 35: // IntConst
		if (words[position].first == "INTCON")
		{
			answer.push_back(words[position]);
			return {position + 1, true};
		}
		else
			return {position, false};
		break;
	case 36: // decimal-const
	case 37: // nonzero-digit
	case 38: // UnaryOp
		if (matchType(dict["+"], position).second)
			position++;
		else if (matchType(dict["-"], position).second)
			position++;
		else if (matchType(dict["!"], position).second)
			position++;
		else
		{
			rollback(size);
			return original_pos;
		}
		answer.push_back({"UnaryOp", ""});
		return {position, true};
		break;
	case 39: // ConstInitVal
		newposition = matchType(dict["ConstExp"], position);
		if (newposition.second)
		{
			answer.push_back({"ConstInitVal", ""});
			return newposition;
		}

		newposition = matchType(dict["{"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["ConstInitVal"], position);
		if (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict[","], position);
			while (newposition.second)
			{
				position = newposition.first;

				newposition = matchType(dict["ConstInitVal"], position);
				if (!newposition.second)
				{
					rollback(size);
					return original_pos;
				}
				position = newposition.first;

				newposition = matchType(dict[","], position);
			}
		}

		newposition = matchType(dict["}"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"ConstInitVal", ""});
		return {position, true};
		break;
	case 40: // ConstDef
		newposition = matchType(dict["Ident"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		newposition = matchType(dict["["], position);
		while (newposition.second)
		{
			position = newposition.first;

			newposition = matchType(dict["ConstExp"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["]"], position);
			if (!newposition.second)
			{
				rollback(size);
				return original_pos;
			}
			position = newposition.first;

			newposition = matchType(dict["["], position);
		}
		newposition = matchType(dict["="], position);
		if (!newposition.second)
		{
			answer.push_back({"ConstDef", ""});
			return {position, true};
		}

		position = newposition.first;

		newposition = matchType(dict["ConstInitVal"], position);
		if (!newposition.second)
		{
			rollback(size);
			return original_pos;
		}
		position = newposition.first;

		answer.push_back({"ConstDef", ""});
		return {position, true};
		break;
	default:
		if (words[position].second == str[type - 40])
		{
			answer.push_back(words[position]);
			return {position + 1, true};
		}
		else
			return {position, false};
		break;
	}
}

std::vector<std::pair<std::string, std::string>> grammatical::resolve(std::vector<std::pair<std::string, std::string>> context)
{
	answer.clear();
	words = context;
	int position = matchType(dict["CompUnit"], 0).first;
	return answer;
}